public class MaxSubArray {
    // 最大子数组和
    // https://leetcode.cn/problems/maximum-subarray/
    public int maxSubArray(int[] nums) {
        // dp[i]表示以第i个元素为结尾的最大子数组的和
        // dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
        int len = nums.length;
        int[] dp = new int[len+1];
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= len; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i-1], nums[i-1]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }

    /**
     * 空间优化，因为在填dp表的时候只需要使用到前一个位置的数据，所以可以使用一个变量来记录前一个位置的数据
     * @param nums
     * @return
     */
    public int maxSubArray1(int[] nums) {
        // dp[i]表示以第i个元素为结尾的最大子数组的和
        // dp[i] = Math.max(dp[i-1] + nums[i], nums[i])
        int len = nums.length;
        int prev = 0;
        int ret = -0x3f3f3f3f;
        for (int i = 1; i <= len; i++) {
            int tmp = Math.max(prev + nums[i-1], nums[i-1]);
            ret = Math.max(ret, tmp);
            prev = tmp;
        }
        return ret;
    }

    /**
     * 贪心
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        // 贪心：通过sum来记录前i个元素和，如果前i个元素的和小于0，那么就不将前i个元素作为最终结果加进去
        int sum = 0;
        int ret = -0x3f3f3f3f;
        for (int i = 0; i < nums.length; i++) {
            ret = Math.max(ret, sum + nums[i]);
            sum = Math.max(sum + nums[i], 0);
        }
        return ret;
    }
}
